package leetcode.D100.T55;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-08-12 10:05:33 星期四
 */

public class Solution {
    /**
     * 解法一：相当于是遍历，但是使用了队列，空间复杂度较高
     */
    /*public boolean canJump(int[] nums) {
        if(nums.length == 1) {
            return true;
        }
        Deque<Integer> queue = new LinkedList<>();
        boolean[] reached = new boolean[nums.length];
        queue.push(0);
        while(!queue.isEmpty()) {
            int idx = queue.getFirst();
            queue.removeFirst();
            for(int i=1; i<=nums[idx]; ++i) {
                int next = idx + i;
                if(next == nums.length - 1) {
                    return true;
                }
                if(idx + nums[idx] >= next + nums[next]) {
                    continue;
                }
                if(!reached[next]) {
                    reached[next] = true;
                    queue.addLast(next);
                }
            }
        }
        return false;
    }*/

    /**
     * 解法二：不借助队列直接实现，这样既降低了空间空间复杂度，也一定程度上降低了时间复杂度
     */
    /*public boolean canJump(int[] nums) {
        int reach = nums[0];
        for(int i=0; i<nums.length; ++i) {
            if(reach >= nums.length-1) {
                return true;
            }
            if(i > reach) {
                return false;
            }
            if(i+nums[i] > reach) {
                reach = i + nums[i];
            }
        }
        return false;
    }*/

    // 二刷
    public boolean canJump(int[] nums) {
        int maxRange = nums[0];
        for (int i=0; i<nums.length; ++i) {
            if (maxRange >= nums.length-1)
                return true;
            if (maxRange < i)
                return false;
            maxRange = Math.max(maxRange, nums[i] + i);
        }
        return false;
    }
}
